package gbench.sandbox.record.cph;

import org.junit.jupiter.api.Test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Stack;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.stream.Collectors;
import java.util.stream.Stream;
import gbench.common.tree.LittleTree;

/**
 * 全排列的基本思想就是构造出一种树形结构，然后对这个树形结构的给予遍历，提取出叶子的节点的路径即可
 * 友谊这里有两种思路：
 * 1）这棵树不存在需要给予建立，然后遍历，即创建法
 * 2）这数已经存在，直接给予遍历即可，即 检索法
 * 
 * 树形结构的 创建法与检索法 生成全排列的演示
 * 
 * @author gbench
 *
 */
public class JunitCph2 {

    public static class DataEngine {

        /**
         * 数据引擎
         * 
         * @param capacity 数据引擎的空间大小
         */
        DataEngine(final int capacity) {
            this.cache = new Object[capacity];
        }

        /**
         * 
         * 指针结构的示例 <br>
         * (pos:T) 表示T类型额一个数据节点的指针<br>
         * 
         * 空间的连续性，被可以用来表达层级关系的示例<br>
         * 
         * 数组元素的比邻关系来表示数据的层级关系 ： <br>
         * [父节点][子节点] <br>
         * [根节点][第一级子节点][第二级子节点][...][第n级子节点] <br>
         * 结构标记 Elem 是指针结构,本身不存放数据，而之保存数据地址 <br>
         * 
         * pos 指向元素内容。 节点的值内容位于pos所指向的数据<br>
         * 
         * @author gbench
         *
         */
        class Elem<T> {

            /**
             * 元素位于cache中的位置
             * 
             * @param pos [0,pos]就是elem所表示的数据
             */
            public Elem(int pos) {
                this.pos = pos;
            }

            /**
             * 返回父节点
             * 
             * @return
             */
            public Elem<T> getParent() {
                return pos <= 0 ? null : DataEngine.this.getElem(pos - 1);
            }

            /**
             * 提取元素的值
             * 
             * @return
             */
            public T value() {
                return DataEngine.this.readAt(pos);
            }

            /**
             * 提取元素的
             * 
             * @return 从根节点到当前节点上额数据序列
             */
            @SuppressWarnings("unchecked")
            public T[] path() {
                return (T[]) DataEngine.this.read(0, this.pos + 1);
            }

            private int pos; // 数据书写位置
        }

        /**
         * 在位置 i 处写入 o
         * 
         * @param i 书写地址
         * @param o 书写内容
         */
        public void set(int i, Object o) {
            if (i >= DataEngine.this.offset.get()) {
                DataEngine.this.offset.set(i + 1);
            }
            this.cache[i] = o;
        }

        /**
         * 把数据写入内存
         * 
         * @param oo 待写入的数据
         */
        public final void resetAndWrite(final Object... oo) {
            this.reset();
            this.write(oo);
        }

        /**
         * 把数据写入内存
         * 
         * @param oo 待写入的数据
         */
        public final void write(final Object... oo) {
            for (var o : oo) {
                this.cache[offset.getAndIncrement()] = o;
            }
        }

        @SuppressWarnings("unchecked")
        public <T> T[] read(int start) {
            return (T[]) Arrays.copyOfRange(DataEngine.this.cache, start, DataEngine.this.offset.get());
        }

        /**
         * 读数据
         * 
         * @param pos    开始位置
         * @param length 读取数据的长度
         * @return 数据长度
         */
        public final Object[] read(final int pos, int length) {
            final var oo = Arrays.copyOfRange(this.cache, pos, pos + length);
            return oo;
        }

        /**
         * 读取 cache 中个数据内容
         * 
         * @param <T>          对象的类型
         * @param pos_in_cache 对象地址,address of elem
         * @return 对象结构
         */
        @SuppressWarnings("unchecked")
        public final <T> T readAt(final int pos_in_cache) {
            return (T) this.cache[pos_in_cache];
        }

        /**
         * 获取object_pool对象结构
         * 
         * @param <T>                元素类型
         * @param pos_in_object_pool 对象对峙
         * @return Elem 类型而机构
         */
        @SuppressWarnings("unchecked")
        public final <T> Elem<T> getElem(final int pos_in_object_pool) {
            return (Elem<T>) this.elemsPool.get(pos_in_object_pool);
        }

        /**
         * 数据重置
         * 
         * @return
         */
        public DataEngine reset() {
            return this.reset(0);
        }

        /**
         * 数据重置
         * 
         * @return
         */
        public DataEngine reset(int _offset) {
            offset.set(_offset);
            return this;
        }

        /**
         * 数据缓存是为空白
         * 
         * @return
         */
        public boolean isEmpty() {
            return this.offset.get() == 0;
        }

        /**
         * 数据缓存是否写满
         * 
         * @return
         */
        public boolean isFull() {
            return this.offset.get() == this.cache.length;
        }

        /**
         * elemsPool 是对内容的抽象
         */
        final Map<Integer, Elem<?>> elemsPool = new HashMap<>();

        /**
         * 生成一个数据节点<br>
         * cons 是 construct 的简写
         * 
         * 注意 这个cons函数创建了 一种父子的结构关系 <br>
         * Elem 的 最大特点 就是 只需要通过一个 pos 结构:<br>
         * 1) 它即是 Elem 的值索引 地址 <br>
         * 2) 也是 Elem 的对象索引 地址 <br>
         * 3）同时 pos 也定义了 Elem 元素的 结果关系，<br>
         * 父节点的 pos=子节点的pos-1, 即 Elem父子关系是pos的函数，<br>
         * 粗略地说pos 还是一种关系 <br>
         * 所以 pos 的语意 极为丰富。切记 不要 把 pos 理解成 一种含义，这样的话 会搞糊涂了 <br>
         * 
         * 通过 pos 我们可以发现：<br>
         * 1）值 与 类型 的关系，类型 就是 值的意义范畴。或者说 类型就是对值 的理解。 <br>
         * 2）当一个值是空间一种个地址的时候，可以实一个偏移量（比喻一个数组的索引），<br>
         * （地址 + 类型）就是一种指针结构，<br>
         * 即对为值 赋予了 专们，专业，特定 理解 而 得到概念。<br>
         * 由于 地址是内容的存取索引，所以 地址的运算<br>
         * 即 地址加减运算 可以 获得的到 另一个 对象的值，<br>
         * 于是 地址 就拥有 了 关系 运算的意义。这就是 为何 c 语言的指针 令人理解的含义。<br>
         * 即 对象地址 可以表达了 对象的关系。用地址表示关系，这在java中不常见，但是也是可以借用的。<br>
         * Elem就是用地址来定义父子关系的。
         * 
         * @param <T>    节点元素的内容
         * @param value  节点元素的内容
         * @param parent 父节点
         * @return 节点元素
         */
        @SuppressWarnings("unchecked")
        public <T> Elem<T> cons(T value, Elem<T> parent) {
            int pos = -1; // 待生成的子节点的 位置地址

            if (parent == null) {// 从0开始
                pos = 0;
                this.resetAndWrite(value);
            } else { // 直接在parent之后写入子节点信息
                this.set(pos = parent.pos + 1, value);
            }

            // 对象写入对象池中给予注册
            return (Elem<T>) elemsPool.computeIfAbsent(pos, _k -> new Elem<T>(_k)); // 使用数据缓存
        }

        @SuppressWarnings("unchecked")
        public <T> Stream<Elem<T>> cph(T[]... tts) {
            return Stream.of(tts).reduce(Stream.of((Elem<T>) null), (parentS, tt) -> {
                return parentS.flatMap(parent -> Stream.of(tt).map(t -> this.cons(t, parent)));
            }, (a, b) -> a);
        }

        final AtomicInteger offset = new AtomicInteger(0); // 当前可以书写的位置,offset的前一位置为有效数据位置。
        final Object[] cache; // 数据缓存
    } // Store

    @SuppressWarnings("unchecked")
    public <T> T[] A(T... ts) {
        return ts;
    }

    public void println(Object... os) {
        System.out.println(Arrays.deepToString(os));
    }

    /**
     * 检索法代码：
     * 1亿条数据历时7.06s, 终于达到1过亿的数据量的处理了。
     */
    @Test
    public void foo() {
        final var dataEngine = new DataEngine(100);
        final Object[] a = A(1, 2, 3, 4, 5, 6, 7, 8, 9, "x");
        final var ai = new AtomicInteger(); // 计数器
        
        dataEngine.cph(a, a, a, a, a, a, a, a).map(LittleTree.kvp_int(1))
        .filter(e -> e._1() % 1000000 == 0)
        .forEach(e -> {
            println(e._1(), e._2().path());
            ai.getAndIncrement();
        });
        
        println(ai);
    }

    /**
     * 把索引：视为指针的 设计思想。在 java 中使用指针编程。
     * 
     * 检索法 全排列。 <br>
     * 需要注意，树结构，是一种看法，不一定需要真的有一颗标准意义上的树结构。<br>
     * 比如 parnt,children 这样的 属性值，我们可以 选择一种 观察角度，即 把 tts 作为
     * 一种树存储结构来看待，于是他就有树的属性，这是一种高级的看表问题的方式。 只需要一种
     * 
     * @param <T> 数据元素类型
     * @param tts 全排列元素集合
     * @return 全排列
     */
    @SuppressWarnings("unchecked")
    public <T> Stream<List<T>> srch_cph(T[]... tts) {

        /**
         * 把 指针的 操作函数的 封装类<br>
         * (level:tts一维度索引,id:tts的二维索引)
         * @author gbench
         *
         */
        class Node { // (level,id) 二维指针 操作工具类。

            /**
             * 创建一个树形节点，父节点为空，即根节点
             * @param level 层号索引 层指针
             * @param id 层内节点偏移索引 层内节点指针
             */
            public Node(int level, int id) {
                this.level = level;
                this.id = id;
                this.parent = null;
            }

            /**
             * 创建一个树形节点
             * @param level 层号索引 层指针
             * @param id 层内节点偏移索引 层内节点指针
             * @param parent 父节点
             */
            public Node(int level, int id, Node parent) {
                this.level = level;
                this.id = id;
                this.parent = parent;
            }

            /**
             * 是否是叶子节点
             * 
             * @return
             */
            public boolean isLeaf() {
                return this.getChildern() == null;
            }

            /**
             * 提取节点的子节点
             * @return
             */
            public List<Node> getChildern() {
                if (level >= tts.length - 1) {
                    return null;
                } else {
                    final var children_level_ = level+1;
                    final var n = tts[children_level_].length; // 子节点数量
                    
                    return Stream.iterate(0, i -> i + 1).limit(n)
                            .map(i -> new Node(children_level_, i, this))
                            .collect(Collectors.toList());
                }
            }

            /**
             * 提取路径
             * @return
             */
            @SuppressWarnings("unused")
            public List<T> path2() {
                return Stream.iterate(this, e -> e != null, e -> e.parent).map(Node::getValue)
                        .reduce(new LinkedList<T>(), (aa, a) -> {
                            aa.push(a);
                            return aa;
                        }, (a, b) -> a);
            }

            /**
             * 路径结构
             * @return
             */
            public List<T> path() {
                return Stream.iterate(this, e -> e != null, e -> e.parent).map(Node::getValue).collect(Collectors.toList());
            }

            /**
             * 提取节点值，节点值：需要把(level,id),拼接成指针来获取。
             * @return
             */
            public T getValue() {
                if (this.level < 0)
                    return null;
                else
                    return tts[this.level][id];
            }

            public String toString() {
                return this.getValue() + "";
            }

            final Node parent; // 父节点
            final int level; // 阶层好
            final int id; // 阶层内的节点编号
        }

        final var root = new Node(-1, -1); // 创建根节点
        final var stack = new Stack<Node>(); // 遍历堆栈
        
        stack.push(root);  // 根节点入栈
        return Stream.iterate(root, e -> e!=null, e -> {
            if (stack.empty()) { // 空栈则结束执行
                // 由于iterate的hasNext是根据前一个元素类判断结束标记的，因此用stack.empty() 遗漏掉以数据元素
                // 特此 使用null 作为hasNext结尾标记，这样就要求Stream中不能含有null元素。用null作为结束一般是没有问题
                // 若需要Stream包含有null，则需要定义一个特殊结束标记节点 在这里给予返回
                return null; // 退出执行标记，
            } else { // stack 费控
                final var node = stack.pop(); // 提取节点
                if (!node.isLeaf()) {
                    node.getChildern().forEach(stack::push);
                }
                return node;
            }
        }).filter(e -> e.isLeaf()).map(Node::path);
    }

    /**
     * 检索法数据全排列
     */
    @Test
    public void bar() {
        final Object[] a = A(1, 2, 3, 4, 5, 6, 7, 8, 9, "x"); // 要素
        final var ai = new AtomicInteger(); // 计数器
        
        this.srch_cph(a, a, a, a, a, a, a, a).map(LittleTree.kvp_int(1))
        .filter(e -> e._1() % 1000000 == 0)
        .forEach(e -> {
            println(e);
            ai.getAndIncrement();
        });
        
        println(ai);
    }

}
